package top.ivansong92.example.leetcode.learning.other.string;

import org.junit.Test;

import java.util.*;

public class TestExamp {

    private static String s = "";

    static {
        s += "aabbccddeeffgghhii";
//        for (int i = 0; i < Integer.MAX_VALUE - 20; i++) {
//            s += ('j' + i % 16);
//        }
        s += "z";
    }

    @Test
    public void test1() {


//        char[] chars = (Integer.MAX_VALUE + "").toCharArray();
//        reverseString(chars);
//        for (char ch : chars) {
//            System.out.printf("" + (ch - '0'));
//        }
//        System.out.println();
//        System.out.println(Integer.valueOf("-0000123"));
//        System.out.println(Integer.MAX_VALUE);
//        System.out.println(Integer.MIN_VALUE);
//        System.out.println(reverse1(-123456));
//        Long res = 123L;
//        res = res + Integer.MAX_VALUE;
//        System.out.println(res);

        System.out.println(firstUniqChar1(s));
    }

    @Test
    public void test2() {
        System.out.println(firstUniqChar2(s));
    }


    /**
     * 反转字符串
     * https://leetcode-cn.com/explore/interview/card/top-interview-questions-easy/5/strings/32/
     *
     * @param s
     */
    public void reverseString(char[] s) {
        if (s == null || s.length < 1) {
            return;
        }
        int i = 0, j = s.length - 1;
        while (i < j) {
            char temp = s[j];
            s[j--] = s[i];
            s[i++] = temp;
        }
    }

    /**
     * 整数反转
     * https://leetcode-cn.com/explore/interview/card/top-interview-questions-easy/5/strings/33/
     *
     * @param x
     * @return
     */
    public int reverse(int x) {
        if (x < 10 && x > -10) {
            return x;
        }
        String s = Integer.toString(x);
        char[] chars = s.toCharArray();
        if (x < 0) {
            chars = Arrays.copyOfRange(chars, 1, chars.length);
        }
        int i = 0, j = chars.length - 1;
        while (i < j) {
            char temp = chars[j];
            chars[j--] = chars[i];
            chars[i++] = temp;
        }
        String re = new String(chars);
        if (x < 0) {
            re = "-" + re;
        }
        try {

            return Integer.parseInt(re);
        } catch (NumberFormatException e) {
            return 0;
        }
    }

    public int reverse1(int x) {
        if (x < 10 && x > -10) {
            return x;
        }
        Long max = new Long(Integer.MAX_VALUE);
        Long min = new Long(Integer.MIN_VALUE);
        long res = 0L;
        for (int temp = x; temp != 0; temp = temp / 10) {
            res = res * 10 + temp % 10;
        }
        if (max.compareTo(res) < 0 || min.compareTo(res) > 0) {
            return 0;
        }
        return new Long(res).intValue();
    }


    public int firstUniqChar(String s) {
        if (s == null || s.length() < 1) {
            return -1;
        }

        if (s.length() == 1) {
            return 0;
        }

        Map<Character, Integer> map = new HashMap<>();
        char[] chars = s.toCharArray();
        for (char ch : chars) {
            if (map.get(ch) != null) {
                map.put(ch, 2);
            } else {
                map.put(ch, 1);
            }
        }

        for (int i = 0; i < chars.length; i++) {
            if (map.get(chars[i]) == 1) {
                return i;
            }
        }

        return -1;
    }

    public int firstUniqChar1(String s) {
        if (s == null || s.length() < 1) {
            return -1;
        }

        if (s.length() == 1) {
            return 0;
        }


        int min = s.length();
        for (char ch = 'a'; ch <= 'z'; ch++) {
            int left = s.indexOf(ch);
            int right = s.lastIndexOf(ch);
            if (left != -1 && left == right && min > left) {
                min = left;
            }
        }

        return min < s.length() ? min : -1;
    }


    public int firstUniqChar2(String s) {
        if (s == null || s.length() < 1) {
            return -1;
        }

        if (s.length() == 1) {
            return 0;
        }

        Integer[] chs = new Integer[26];
        char[] chars = s.toCharArray();

        for (int i = 0; i < chars.length; i++) {
            int val = chars[i] - 'a';
            Integer indexVal = chs[val];
            if (indexVal == null) {
                chs[val] = i;
                continue;
            }

            if (indexVal >= 0) {
                chs[val] = -1;
            }
        }

        int min = s.length();
        for (Integer ch : chs) {
            if (ch == null || ch < 0) {
                continue;
            }
            if (ch < min) {
                min = ch;
            }
        }

        return min < s.length() ? min : -1;
    }

    @Test
    public void test3() {
        System.out.println(isAnagram("anagram", "nagaram"));
    }

    public boolean isAnagram(String s, String t) {
        if (s == null || t == null || s.length() != t.length()) {
            return false;
        }

        Integer[] sChars = new Integer[26];
        for (char ch : s.toCharArray()) {
            int plus = ch - 'a';
            Integer val = sChars[plus];
            if (val == null) {
                sChars[plus] = 1;
                continue;
            }
            sChars[plus] = val + 1;
        }

        Integer[] tChars = new Integer[26];

        for (char ch : t.toCharArray()) {
            int plus = ch - 'a';
            Integer val = tChars[plus];
            if (val == null) {
                tChars[plus] = 1;
                continue;
            }
            tChars[plus] = val + 1;
        }

        for (int i = 0; i < 26; i++) {
            Integer tVal = tChars[i];
            Integer sVal = sChars[i];
            if (tVal == null && sVal == null) {
                continue;
            }
            if (tVal == null && sVal != null) {
                return false;
            }
            if (tVal != null && sVal == null) {
                return false;
            }

            if (tVal.compareTo(sVal) != 0) {
                return false;
            }

        }
        return true;
    }


    public boolean isAnagram1(String s, String t) {
        if (s == null || t == null || s.length() != t.length()) {
            return false;
        }

        int len = s.length();
        int[] chars = new int[26];
        for (int i = 0; i < len; i++) {
            chars[s.charAt(i) - 'a'] += 1;
            chars[t.charAt(i) - 'a'] -= 1;
        }

        for (int i : chars) {
            if (i != 0) {
                return false;
            }
        }
        return true;
    }


    @Test
    public void test4() {
        System.out.println(isPalindrome("race a car"));
    }

    /**
     * 验证回文字符串
     * https://leetcode-cn.com/explore/interview/card/top-interview-questions-easy/5/strings/36/
     *
     * @param s
     * @return
     */
    public boolean isPalindrome(String s) {
        if (s == null) {
            return false;
        }
        if (s.length() <= 1) {
            return true;
        }
        String low = s.toLowerCase();
        char[] chars = new char[low.length()];
        int cpLen = 0;
        for (int i = 0; i < low.length(); i++) {
            char ch = low.charAt(i);
            int num_match = ch - '0';
            int apl_match = ch - 'a';
            if ((num_match >= 0 && num_match <= 9) || (apl_match >= 0 && apl_match < 26)) {
                chars[cpLen++] = ch;
            }
        }
        if (cpLen == 0) {
            return true;
        }
        chars = Arrays.copyOfRange(chars, 0, cpLen);
        int i = 0, j = cpLen - 1;
        while (i < j) {
            if (chars[i++] != chars[j--]) {
                return false;
            }
        }
        return true;
    }

    public boolean isPalindrome1(String s) {
        if (s == null) {
            return false;
        }
        if (s.length() <= 1) {
            return true;
        }

        String low = s.toLowerCase();
        int i = 0, j = low.length() - 1;
        while (i <= j) {
            char ch_i = low.charAt(i);
            if (!matchChar(ch_i)) {
                i++;
                continue;
            }
            char ch_j = low.charAt(j);
            if (!matchChar(ch_j)) {
                j--;
                continue;
            }
            if (ch_i != ch_j) {
                return false;
            }
            i++;
            j--;
        }
        return true;
    }


    private boolean matchChar(char ch) {
        int num_match = ch - '0';
        int apl_match = ch - 'a';
        if ((num_match >= 0 && num_match <= 9) || (apl_match >= 0 && apl_match < 26)) {
            return true;
        }
        return false;
    }


    @Test
    public void test5() {
        System.out.println(myAtoi("   +0 123"));
        System.out.println(Integer.parseInt("+1"));
    }

    /**
     * 字符串转换整数 (atoi)
     * https://leetcode-cn.com/explore/interview/card/top-interview-questions-easy/5/strings/37/
     *
     * @param str
     * @return
     */

    public int myAtoi(String str) {
        if (str == null || str.length() < 1) {
            return 0;
        }

        char[] chars = new char[str.length()];
        int len = 0;
        for (int i = 0; i < str.length(); i++) {
            char ch = str.charAt(i);
            if (ch == ' ' && len == 0) {
                continue;
            }
            if (len == 0 && (ch == '-' || ch == '+')) {
                chars[len++] = ch;
                continue;
            }


            int numChe = ch - '0';
            if (numChe < 0 || numChe > 9) {
                break;
            }

            chars[len++] = ch;
        }

        if (len == 0 || (len == 1 && (chars[0] == '-' || chars[0] == '+'))) {
            return 0;
        }

        try {
            return Integer.parseInt(new String(Arrays.copyOfRange(chars, 0, len)));
        } catch (NumberFormatException e) {
            if (chars[0] == '-') {
                return Integer.MIN_VALUE;
            } else {
                return Integer.MAX_VALUE;
            }
        }
    }


    @Test
    public void test6() {
        System.out.println(strStr("a", "a"));
    }

    /**
     * 实现strStr()
     * https://leetcode-cn.com/explore/interview/card/top-interview-questions-easy/5/strings/38/
     *
     * @param haystack
     * @param needle
     * @return
     */
    public int strStr(String haystack, String needle) {
        if (needle == null || needle.length() < 1) {
            return 0;
        }

        if (haystack == null || haystack.length() < needle.length()) {
            return -1;
        }


        if (haystack.startsWith(needle)) {
            return 0;
        }

        if (haystack.endsWith(needle)) {
            return haystack.length() - needle.length();
        }
        String[] splits = haystack.split(needle);

        if (splits == null || splits.length == 0) {
            return 0;
        }
        if (splits.length == 1) {
            return -1;
        }
        return splits[0].length();
    }

    public int strStr1(String haystack, String needle) {
        if (needle == null || needle.length() < 1) {
            return 0;
        }

        if (haystack == null || haystack.length() < needle.length()) {
            return -1;
        }
        return haystack.indexOf(needle);
    }


    /**
     * 最长公共前缀
     * https://leetcode-cn.com/explore/interview/card/top-interview-questions-easy/5/strings/40/
     *
     * @param strs
     * @return
     */
    public String longestCommonPrefix(String[] strs) {
        if (strs == null || strs.length < 1) {
            return "";
        }

        int min = Integer.MAX_VALUE;
        for (String str : strs) {
            min = Math.min(str.length(), min);
        }

        if (min < 1) {
            return "";
        }
        char[] chars = new char[min];
        int len = 0;

        out:
        for (int i = 0; i < min; i++) {
            char ch = strs[0].charAt(i);
            for (String str : strs) {
                if (str.charAt(i) != ch) {
                    break out;
                }
            }
            chars[len ++] = ch;
        }
        if (len < 1) {
            return "";
        }
        return new String(Arrays.copyOfRange(chars, 0 , len));
    }
}
